class AllSort
{
	public static void main(String[] args) 
	{
		int[] data = {3,1,5,7,2,4,9,6};
		printData(data);
		//System.out.println("len: "+data.length);
		//insertSort(data);
		shellSort(data);
		printData(data);
	}
	//插入排序
	public static void insertSort(int[] data){
		int len = data.length;
		for(int i=1;i<len;i++){
			if (data[i]<data[i-1]) {
				int tmp = data[i];
				int j = 0 ;
				for(j = i-1;j>=0;j--){
					if (data[j]>tmp) {
						data[j+1]=data[j];
					}else{
						break;
					}
				}
				data[j+1]=tmp;
			}
		}
	}
	//索尔排序
	public static void shellSort(int[] data){
		int d = data.length/2;
		while(true){
			for(int x=0;x<d;x++){
				for(int i=x+d;i<data.length;i+=d){
					int j = i-d;
					int tmp = data[i];
					for(;j>=0&&tmp<data[j];j-=d){
						data[j+d]=data[j];
					}
					data[j+d]=tmp;
				}
			}
			if(d==1){
				break;
			}
			d/=2;
		}
		}
		
	
	public static void printData(int[] data){
		for(int i : data){
			System.out.print(i+" ");
		}
		System.out.println();	
	}
}
